package LeetCode.Leet300_399.Leet370_379.Leet377;

/**
 * @ClassName Solution_2
 * @Author 孙天赐
 * @Date 2025/9/25 17:24
 * @Description TODO: 方法二   动态规划（一维dp）  1ms 92.05%
 *                  如果求组合数就是外层for循环遍历物品，内层for遍历背包。
 *                  如果求排列数就是外层for遍历背包，内层for循环遍历物品。
 */
class Solution_2 {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < nums.length; j++) {
                if (i >= nums[j]) {
                    dp[i] = dp[i] + dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
}
